/*
leetcode 238: https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150

题目描述：除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

 

示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
 

提示：

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内
 

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

解题思路：
1. 

*/
#include <iostream>
#include <vector>
 using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
            std::vector<int> answer(nums.size(), 1);
            int left = 0, right = nums.size() - 1;
            int lp = 1, rp = 1;

            while (right >= 0 && left < nums.size()) {

                answer[left] = answer[left]*lp; //1 3 2
                answer[right] = answer[right]*rp; // 1 3 6
                //cout << answer[right] << endl;
                
                lp = lp*nums[left];
                //cout << lp << endl;
                left++;
                rp = rp*nums[right];
                //cout << rp << endl;
                right--;
                
            }
            return answer;
        
    }
};

/*
answer = 1 1 1 
 nums = 1 2 3 
 left=0 right=2
 lp=rp=1
 nums[0]=1
 nums[1]=2
 nums[2]=3
 
 while right>=0 && left< 3
    answer[0] = answer[0]*lp = 1*1=1
    answer[2] = answer[2]*rp = 1*1=1
    lp = lp*nums[0] = 1*1 =1
    rp = rp*nums[2] = 1*3 =3
    left=1
    right=1

 while
    answer[1] = answer[1]*lp = 1*1=1
    answer[1] = answer[1]*rp = 1*3=3 //3
    lp = lp*nums[1] = 1*2 =2
    rp = rp*nums[1] = 3*2 =6
    left=2
    right=0
while
    answer[2] = answer[2]*lp = 1*2=2 //2
    answer[0] = answer[0]*rp = 1*6=6 //6
    lp = lp*nums[2] = 2*3 =6
    rp = rp*nums[0] = 6*1 =6
    left=3
    right=-1
   
 while 退出
*/
class Solution2 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 1), right(n, 1), result(n, 1);

        // 计算左侧乘积
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        //left[1]=left[0]*nums[0]
        //left[2]=left[1]*nums[1]
        //left[3]=left[2]*nums[2]

        // 计算右侧乘积
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        //right[2]
        //right[1]
        //right[0]

        // 计算最终结果
        for (int i = 0; i < n; i++) {
            result[i] = left[i] * right[i];
        }

        return result;
    }
};

int main() {
    Solution2 solution;
    std::vector<int> nums = {1, 2, 3, 4}; // 示例数组
    std::vector<int> result = solution.productExceptSelf(nums);
    
    std::cout << "Output: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}